{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "D7tqLMoKF6uq"
   },
   "source": [
    "Deep Learning\n",
    "=============\n",
    "\n",
    "Assignment 6\n",
    "------------\n",
    "\n",
    "After training a skip-gram model in `5_word2vec.ipynb`, the goal of this notebook is to train a LSTM character model over [Text8](http://mattmahoney.net/dc/textdata) data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "MvEblsgEXxrd"
   },
   "outputs": [],
   "source": [
    "# These are all the modules we'll be using later. Make sure you can import them\n",
    "# before proceeding further.\n",
    "from __future__ import print_function\n",
    "import os\n",
    "import numpy as np\n",
    "import random\n",
    "import string\n",
    "import tensorflow as tf\n",
    "import zipfile\n",
    "from six.moves import range\n",
    "from six.moves.urllib.request import urlretrieve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "executionInfo": {
     "elapsed": 5993,
     "status": "ok",
     "timestamp": 1445965582896,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "RJ-o3UBUFtCw",
    "outputId": "d530534e-0791-4a94-ca6d-1c8f1b908a9e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found and verified text8.zip\n"
     ]
    }
   ],
   "source": [
    "url = 'http://mattmahoney.net/dc/'\n",
    "\n",
    "def maybe_download(filename, expected_bytes):\n",
    "  \"\"\"Download a file if not present, and make sure it's the right size.\"\"\"\n",
    "  if not os.path.exists(filename):\n",
    "    filename, _ = urlretrieve(url + filename, filename)\n",
    "  statinfo = os.stat(filename)\n",
    "  if statinfo.st_size == expected_bytes:\n",
    "    print('Found and verified %s' % filename)\n",
    "  else:\n",
    "    print(statinfo.st_size)\n",
    "    raise Exception(\n",
    "      'Failed to verify ' + filename + '. Can you get to it with a browser?')\n",
    "  return filename\n",
    "\n",
    "filename = maybe_download('text8.zip', 31344016)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "executionInfo": {
     "elapsed": 5982,
     "status": "ok",
     "timestamp": 1445965582916,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "Mvf09fjugFU_",
    "outputId": "8f75db58-3862-404b-a0c3-799380597390"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Data size 100000000\n"
     ]
    }
   ],
   "source": [
    "def read_data(filename):\n",
    "  f = zipfile.ZipFile(filename)\n",
    "  for name in f.namelist():\n",
    "    return tf.compat.as_str(f.read(name))\n",
    "  f.close()\n",
    "  \n",
    "text = read_data(filename)\n",
    "print('Data size %d' % len(text))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ga2CYACE-ghb"
   },
   "source": [
    "Create a small validation set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "executionInfo": {
     "elapsed": 6184,
     "status": "ok",
     "timestamp": 1445965583138,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "w-oBpfFG-j43",
    "outputId": "bdb96002-d021-4379-f6de-a977924f0d02"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99999000 ons anarchists advocate social relations based upon voluntary as\n",
      "1000  anarchism originated as a term of abuse first used against earl\n"
     ]
    }
   ],
   "source": [
    "valid_size = 1000\n",
    "valid_text = text[:valid_size]\n",
    "train_text = text[valid_size:]\n",
    "train_size = len(train_text)\n",
    "print(train_size, train_text[:64])\n",
    "print(valid_size, valid_text[:64])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Zdw6i4F8glpp"
   },
   "source": [
    "Utility functions to map characters to vocabulary IDs and back."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "executionInfo": {
     "elapsed": 6276,
     "status": "ok",
     "timestamp": 1445965583249,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "gAL1EECXeZsD",
    "outputId": "88fc9032-feb9-45ff-a9a0-a26759cc1f2e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unexpected character: ï\n",
      "1 26 0 0\n",
      "a z  \n"
     ]
    }
   ],
   "source": [
    "vocabulary_size = len(string.ascii_lowercase) + 1 # [a-z] + ' '\n",
    "first_letter = ord(string.ascii_lowercase[0])\n",
    "\n",
    "def char2id(char):\n",
    "  if char in string.ascii_lowercase:\n",
    "    return ord(char) - first_letter + 1\n",
    "  elif char == ' ':\n",
    "    return 0\n",
    "  else:\n",
    "    print('Unexpected character: %s' % char)\n",
    "    return 0\n",
    "  \n",
    "def id2char(dictid):\n",
    "  if dictid > 0:\n",
    "    return chr(dictid + first_letter - 1)\n",
    "  else:\n",
    "    return ' '\n",
    "\n",
    "print(char2id('a'), char2id('z'), char2id(' '), char2id('ï'))\n",
    "print(id2char(1), id2char(26), id2char(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lFwoyygOmWsL"
   },
   "source": [
    "Function to generate a training batch for the LSTM model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "executionInfo": {
     "elapsed": 6473,
     "status": "ok",
     "timestamp": 1445965583467,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "d9wMtjy5hCj9",
    "outputId": "3dd79c80-454a-4be0-8b71-4a4a357b3367"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['ons anarchi', 'when milita', 'lleria arch', ' abbeys and', 'married urr', 'hel and ric', 'y and litur', 'ay opened f', 'tion from t', 'migration t', 'new york ot', 'he boeing s', 'e listed wi', 'eber has pr', 'o be made t', 'yer who rec', 'ore signifi', 'a fierce cr', ' two six ei', 'aristotle s', 'ity can be ', ' and intrac', 'tion of the', 'dy to pass ', 'f certain d', 'at it will ', 'e convince ', 'ent told hi', 'ampaign and', 'rver side s', 'ious texts ', 'o capitaliz', 'a duplicate', 'gh ann es d', 'ine january', 'ross zero t', 'cal theorie', 'ast instanc', ' dimensiona', 'most holy m', 't s support', 'u is still ', 'e oscillati', 'o eight sub', 'of italy la', 's the tower', 'klahoma pre', 'erprise lin', 'ws becomes ', 'et in a naz', 'the fabian ', 'etchy to re', ' sharman ne', 'ised empero', 'ting in pol', 'd neo latin', 'th risky ri', 'encyclopedi', 'fense the a', 'duating fro', 'treet grid ', 'ations more', 'appeal of d', 'si have mad']\n",
      "['ists advoca', 'ary governm', 'hes nationa', 'd monasteri', 'raca prince', 'chard baer ', 'rgical lang', 'for passeng', 'the nationa', 'took place ', 'ther well k', 'seven six s', 'ith a gloss', 'robably bee', 'to recogniz', 'ceived the ', 'icant than ', 'ritic of th', 'ight in sig', 's uncaused ', ' lost as in', 'cellular ic', 'e size of t', ' him a stic', 'drugs confu', ' take to co', ' the priest', 'im to name ', 'd barred at', 'standard fo', ' such as es', 'ze on the g', 'e of the or', 'd hiver one', 'y eight mar', 'the lead ch', 'es classica', 'ce the non ', 'al analysis', 'mormons bel', 't or at lea', ' disagreed ', 'ing system ', 'btypes base', 'anguages th', 'r commissio', 'ess one nin', 'nux suse li', ' the first ', 'zi concentr', ' society ne', 'elatively s', 'etworks sha', 'or hirohito', 'litical ini', 'n most of t', 'iskerdoo ri', 'ic overview', 'air compone', 'om acnm acc', ' centerline', 'e than any ', 'devotional ', 'de such dev']\n",
      "[' a']\n",
      "['an']\n"
     ]
    }
   ],
   "source": [
    "batch_size=64\n",
    "num_unrollings=10\n",
    "\n",
    "class BatchGenerator(object):\n",
    "  def __init__(self, text, batch_size, num_unrollings):\n",
    "    self._text = text\n",
    "    self._text_size = len(text)\n",
    "    self._batch_size = batch_size\n",
    "    self._num_unrollings = num_unrollings\n",
    "    segment = self._text_size // batch_size\n",
    "    self._cursor = [ offset * segment for offset in range(batch_size)]\n",
    "    self._last_batch = self._next_batch()\n",
    "  \n",
    "  def _next_batch(self):\n",
    "    \"\"\"Generate a single batch from the current cursor position in the data.\"\"\"\n",
    "    batch = np.zeros(shape=(self._batch_size, vocabulary_size), dtype=np.float)\n",
    "    for b in range(self._batch_size):\n",
    "      batch[b, char2id(self._text[self._cursor[b]])] = 1.0\n",
    "      self._cursor[b] = (self._cursor[b] + 1) % self._text_size\n",
    "    return batch\n",
    "  \n",
    "  def next(self):\n",
    "    \"\"\"Generate the next array of batches from the data. The array consists of\n",
    "    the last batch of the previous array, followed by num_unrollings new ones.\n",
    "    \"\"\"\n",
    "    batches = [self._last_batch]\n",
    "    for step in range(self._num_unrollings):\n",
    "      batches.append(self._next_batch())\n",
    "    self._last_batch = batches[-1]\n",
    "    return batches\n",
    "\n",
    "def characters(probabilities):\n",
    "  \"\"\"Turn a 1-hot encoding or a probability distribution over the possible\n",
    "  characters back into its (most likely) character representation.\"\"\"\n",
    "  return [id2char(c) for c in np.argmax(probabilities, 1)]\n",
    "\n",
    "def batches2string(batches):\n",
    "  \"\"\"Convert a sequence of batches back into their (most likely) string\n",
    "  representation.\"\"\"\n",
    "  s = [''] * batches[0].shape[0]\n",
    "  for b in batches:\n",
    "    s = [''.join(x) for x in zip(s, characters(b))]\n",
    "  return s\n",
    "\n",
    "train_batches = BatchGenerator(train_text, batch_size, num_unrollings)\n",
    "valid_batches = BatchGenerator(valid_text, 1, 1)\n",
    "\n",
    "print(batches2string(train_batches.next()))\n",
    "print(batches2string(train_batches.next()))\n",
    "print(batches2string(valid_batches.next()))\n",
    "print(batches2string(valid_batches.next()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "KyVd8FxT5QBc"
   },
   "outputs": [],
   "source": [
    "def logprob(predictions, labels):\n",
    "  \"\"\"Log-probability of the true labels in a predicted batch.\"\"\"\n",
    "  predictions[predictions < 1e-10] = 1e-10\n",
    "  return np.sum(np.multiply(labels, -np.log(predictions))) / labels.shape[0]\n",
    "\n",
    "def sample_distribution(distribution):\n",
    "  \"\"\"Sample one element from a distribution assumed to be an array of normalized\n",
    "  probabilities.\n",
    "  \"\"\"\n",
    "  r = random.uniform(0, 1)\n",
    "  s = 0\n",
    "  for i in range(len(distribution)):\n",
    "    s += distribution[i]\n",
    "    if s >= r:\n",
    "      return i\n",
    "  return len(distribution) - 1\n",
    "\n",
    "def sample(prediction):\n",
    "  \"\"\"Turn a (column) prediction into 1-hot encoded samples.\"\"\"\n",
    "  p = np.zeros(shape=[1, vocabulary_size], dtype=np.float)\n",
    "  p[0, sample_distribution(prediction[0])] = 1.0\n",
    "  return p\n",
    "\n",
    "def random_distribution():\n",
    "  \"\"\"Generate a random column of probabilities.\"\"\"\n",
    "  b = np.random.uniform(0.0, 1.0, size=[1, vocabulary_size])\n",
    "  return b/np.sum(b, 1)[:,None]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "K8f67YXaDr4C"
   },
   "source": [
    "Simple LSTM Model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "Q5rxZK6RDuGe"
   },
   "outputs": [],
   "source": [
    "num_nodes = 64\n",
    "\n",
    "graph = tf.Graph()\n",
    "with graph.as_default():\n",
    "  \n",
    "  # Parameters:\n",
    "  # Input gate: input, previous output, and bias.\n",
    "  ix = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  im = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ib = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Forget gate: input, previous output, and bias.\n",
    "  fx = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  fm = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  fb = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Memory cell: input, state and bias.                             \n",
    "  cx = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  cm = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  cb = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Output gate: input, previous output, and bias.\n",
    "  ox = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  om = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ob = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Variables saving state across unrollings.\n",
    "  saved_output = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  saved_state = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  # Classifier weights and biases.\n",
    "  w = tf.Variable(tf.truncated_normal([num_nodes, vocabulary_size], -0.1, 0.1))\n",
    "  b = tf.Variable(tf.zeros([vocabulary_size]))\n",
    "  \n",
    "  # Definition of the cell computation.\n",
    "  def lstm_cell(i, o, state):\n",
    "    \"\"\"Create a LSTM cell. See e.g.: http://arxiv.org/pdf/1402.1128v1.pdf\n",
    "    Note that in this formulation, we omit the various connections between the\n",
    "    previous state and the gates.\"\"\"\n",
    "    input_gate = tf.sigmoid(tf.matmul(i, ix) + tf.matmul(o, im) + ib)\n",
    "    forget_gate = tf.sigmoid(tf.matmul(i, fx) + tf.matmul(o, fm) + fb)\n",
    "    update = tf.matmul(i, cx) + tf.matmul(o, cm) + cb\n",
    "    state = forget_gate * state + input_gate * tf.tanh(update)\n",
    "    output_gate = tf.sigmoid(tf.matmul(i, ox) + tf.matmul(o, om) + ob)\n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "  for _ in range(num_unrollings + 1):\n",
    "    train_data.append(\n",
    "      tf.placeholder(tf.float32, shape=[batch_size,vocabulary_size]))\n",
    "  train_inputs = train_data[:num_unrollings]\n",
    "  train_labels = train_data[1:]  # labels are inputs shifted by one time step.\n",
    "\n",
    "  # Unrolled LSTM loop.\n",
    "  outputs = list()\n",
    "  output = saved_output\n",
    "  state = saved_state\n",
    "  for i in train_inputs:\n",
    "    output, state = lstm_cell(i, output, state)\n",
    "    outputs.append(output)\n",
    "\n",
    "  # State saving across unrollings.\n",
    "  with tf.control_dependencies([saved_output.assign(output),\n",
    "                                saved_state.assign(state)]):\n",
    "    # Classifier.\n",
    "    logits = tf.nn.xw_plus_b(tf.concat(0, outputs), w, b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        logits, tf.concat(0, train_labels)))\n",
    "\n",
    "  # Optimizer.\n",
    "  global_step = tf.Variable(0)\n",
    "  learning_rate = tf.train.exponential_decay(\n",
    "    10.0, global_step, 5000, 0.1, staircase=True)\n",
    "  optimizer = tf.train.GradientDescentOptimizer(learning_rate)\n",
    "  gradients, v = zip(*optimizer.compute_gradients(loss))\n",
    "  gradients, _ = tf.clip_by_global_norm(gradients, 1.25)\n",
    "  optimizer = optimizer.apply_gradients(\n",
    "    zip(gradients, v), global_step=global_step)\n",
    "\n",
    "  # Predictions.\n",
    "  train_prediction = tf.nn.softmax(logits)\n",
    "  \n",
    "  # Sampling and validation eval: batch 1, no unrolling.\n",
    "  sample_input = tf.placeholder(tf.float32, shape=[1, vocabulary_size])\n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  reset_sample_state = tf.group(\n",
    "    saved_sample_output.assign(tf.zeros([1, num_nodes])),\n",
    "    saved_sample_state.assign(tf.zeros([1, num_nodes])))\n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input, saved_sample_output, saved_sample_state)\n",
    "  with tf.control_dependencies([saved_sample_output.assign(sample_output),\n",
    "                                saved_sample_state.assign(sample_state)]):\n",
    "    sample_prediction = tf.nn.softmax(tf.nn.xw_plus_b(sample_output, w, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 41
      },
      {
       "item_id": 80
      },
      {
       "item_id": 126
      },
      {
       "item_id": 144
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "executionInfo": {
     "elapsed": 199909,
     "status": "ok",
     "timestamp": 1445965877333,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "RD9zQCZTEaEm",
    "outputId": "5e868466-2532-4545-ce35-b403cf5d9de6"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0: 3.289977 learning rate: 10.000000\n",
      "Minibatch perplexity: 26.84\n",
      "================================================================================\n",
      "xmnjeupohenlqabamfe ssnepda n arlpoofcgejutoku fsdmlueomhahxafl fxaipolsupqabepd\n",
      "md wctna onaklw w pprixtotdddfcu zgqgktseerawk apskdnd fevkorl urvtzemro  ntivwf\n",
      "gaslpepparjaceemurutczff x pttkg hfy qob p  ewg sr hp  otuxt enbcm sdq eoeam iup\n",
      "qf fiix bdolaivirohi ftyyeei txeyx oqkd hyxg tanbofpai piomqrqaaqcczopgqxsredetk\n",
      "  v mnfthqtvodmcftmvbzhhrwqeyzgszlesotdefx x buxte bki nhzrmglogjh  tvdwezzudeo \n",
      "================================================================================\n",
      "Validation set perplexity: 20.04\n",
      "Average loss at step 100: 2.602667 learning rate: 10.000000\n",
      "Minibatch perplexity: 10.99\n",
      "Validation set perplexity: 10.41\n",
      "Average loss at step 200: 2.248658 learning rate: 10.000000\n",
      "Minibatch perplexity: 8.74\n",
      "Validation set perplexity: 8.56\n",
      "Average loss at step 300: 2.103542 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.51\n",
      "Validation set perplexity: 8.03\n",
      "Average loss at step 400: 2.006016 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.56\n",
      "Validation set perplexity: 7.82\n",
      "Average loss at step 500: 1.940605 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.32\n",
      "Validation set perplexity: 6.98\n",
      "Average loss at step 600: 1.911684 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.20\n",
      "Validation set perplexity: 6.87\n",
      "Average loss at step 700: 1.867965 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.45\n",
      "Validation set perplexity: 6.58\n",
      "Average loss at step 800: 1.826559 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.03\n",
      "Validation set perplexity: 6.36\n",
      "Average loss at step 900: 1.830063 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.99\n",
      "Validation set perplexity: 6.17\n",
      "Average loss at step 1000: 1.826074 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.62\n",
      "================================================================================\n",
      "er the counteous kepresed two one nine nine seven a cresg to breck ayser one jin\n",
      " rear and velas criclationt sharmentmmen by the lest is perase food ne wreniemoy\n",
      "a moppit sdpicity heality wortater in one nine five gore nepert peire greation i\n",
      "y line exterby the cilare or lide in leg eive widlle verimided its busk beofzen \n",
      "fionest econogion whened ky luil four nexered sountifoly refuld of enely one sev\n",
      "================================================================================\n",
      "Validation set perplexity: 5.92\n",
      "Average loss at step 1100: 1.775361 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.55\n",
      "Validation set perplexity: 5.69\n",
      "Average loss at step 1200: 1.753849 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.02\n",
      "Validation set perplexity: 5.42\n",
      "Average loss at step 1300: 1.734803 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.89\n",
      "Validation set perplexity: 5.52\n",
      "Average loss at step 1400: 1.744296 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.11\n",
      "Validation set perplexity: 5.42\n",
      "Average loss at step 1500: 1.738733 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.83\n",
      "Validation set perplexity: 5.20\n",
      "Average loss at step 1600: 1.746876 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.50\n",
      "Validation set perplexity: 5.24\n",
      "Average loss at step 1700: 1.711606 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.58\n",
      "Validation set perplexity: 5.21\n",
      "Average loss at step 1800: 1.677461 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.43\n",
      "Validation set perplexity: 5.14\n",
      "Average loss at step 1900: 1.647010 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.10\n",
      "Validation set perplexity: 5.03\n",
      "Average loss at step 2000: 1.699845 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.74\n",
      "================================================================================\n",
      "perical comedy can to that teapallians in drincells a the yething and optic and \n",
      "wereven vorment cakentty propusifically notated the expecited hading cnta of the\n",
      "quates patic maded singing impering truing at muss orthiplemmnt with was velon b\n",
      "raich and toparl ducc assebrastany paing litelined exoppecticmes it be galliany \n",
      "imated turse wyp knimed f top fromms and didepish aksge succent are for up side \n",
      "================================================================================\n",
      "Validation set perplexity: 5.06\n",
      "Average loss at step 2100: 1.687854 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.13\n",
      "Validation set perplexity: 4.95\n",
      "Average loss at step 2200: 1.683015 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.38\n",
      "Validation set perplexity: 4.92\n",
      "Average loss at step 2300: 1.642095 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.94\n",
      "Validation set perplexity: 4.74\n",
      "Average loss at step 2400: 1.659019 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.15\n",
      "Validation set perplexity: 4.78\n",
      "Average loss at step 2500: 1.680215 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.27\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 2600: 1.655603 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.95\n",
      "Validation set perplexity: 4.70\n",
      "Average loss at step 2700: 1.655334 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.48\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 2800: 1.651936 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.64\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 2900: 1.651667 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.66\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 3000: 1.655730 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.18\n",
      "================================================================================\n",
      "t abse have theorila yasy halk varce numbered and many roverods calqual dohnatol\n",
      "n cangles become francess rekistians was fornennals by the withlecable archers p\n",
      "ol peaced georest of schoil the inco enterds roolsimol briggnis not dafusading w\n",
      "uptisconcemitions importal common and long seather is andowid compbeted toodaft \n",
      "forming halld intereded by to erginge seali s fersittegere one nine seven federe\n",
      "================================================================================\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 3100: 1.628490 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.81\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 3200: 1.647497 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 3300: 1.638365 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.12\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 3400: 1.668012 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.37\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 3500: 1.658973 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.46\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 3600: 1.664142 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.39\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 3700: 1.644895 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.97\n",
      "Validation set perplexity: 4.45\n",
      "Average loss at step 3800: 1.641431 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.46\n",
      "Validation set perplexity: 4.60\n",
      "Average loss at step 3900: 1.635605 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.25\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 4000: 1.655683 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.64\n",
      "================================================================================\n",
      "commitate of duptical buse likeness b the the edentike death property thoucher p\n",
      "noda age home arthas be inchinces irclaeferse spap and see seal the lood one nin\n",
      "s missorce from effect of mong hephy feleh to to monarrinaa work see wite charan\n",
      "fine not late on world cause anally ballen two six to misss irelf is zalaces j t\n",
      "lim sea as by feot not undroda itres replate cenker origanaracren chlietion same\n",
      "================================================================================\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 4100: 1.632684 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.29\n",
      "Validation set perplexity: 4.72\n",
      "Average loss at step 4200: 1.633175 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.26\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 4300: 1.621943 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.90\n",
      "Validation set perplexity: 4.62\n",
      "Average loss at step 4400: 1.608427 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.88\n",
      "Validation set perplexity: 4.38\n",
      "Average loss at step 4500: 1.613810 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.13\n",
      "Validation set perplexity: 4.62\n",
      "Average loss at step 4600: 1.612047 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.85\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 4700: 1.624865 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.32\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 4800: 1.632768 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.30\n",
      "Validation set perplexity: 4.48\n",
      "Average loss at step 4900: 1.631152 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.25\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 5000: 1.607295 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.47\n",
      "================================================================================\n",
      "jech one pl so becausesh as fiction the exas grastedly by the docume mack him so\n",
      "watema gamija isritic on seven seven eithe f one nine five cossing baniv genear \n",
      "ultal deaturuting beanking rea b geripo d qa rokithery comes de all by the rasch\n",
      "choositalic an chinase and reconding consively sected his nothan megal wholeguar\n",
      "ware joots with a in them their ridbwaken in not to also fastsport by govation h\n",
      "================================================================================\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 5100: 1.603990 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.10\n",
      "Validation set perplexity: 4.39\n",
      "Average loss at step 5200: 1.591834 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.54\n",
      "Validation set perplexity: 4.33\n",
      "Average loss at step 5300: 1.576628 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.62\n",
      "Validation set perplexity: 4.31\n",
      "Average loss at step 5400: 1.583108 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.10\n",
      "Validation set perplexity: 4.31\n",
      "Average loss at step 5500: 1.565867 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.79\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 5600: 1.579343 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.88\n",
      "Validation set perplexity: 4.25\n",
      "Average loss at step 5700: 1.568711 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.42\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 5800: 1.578333 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.82\n",
      "Validation set perplexity: 4.29\n",
      "Average loss at step 5900: 1.573890 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.99\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 6000: 1.544972 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.02\n",
      "================================================================================\n",
      "lives male is organizationapher mort websocient is counthed his film unitian pre\n",
      "mercher one nine three broad take involved more percation which groups muck to y\n",
      "x ambretejabol camer verobel gararation wnite seven on then laut from privated a\n",
      "ter and a netend provective the drumetout on level world them by proponring is a\n",
      "tes compsefic best earthing rewas thot was contemmer s movier by intilsuty the c\n",
      "================================================================================\n",
      "Validation set perplexity: 4.26\n",
      "Average loss at step 6100: 1.563076 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.12\n",
      "Validation set perplexity: 4.24\n",
      "Average loss at step 6200: 1.533008 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.93\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 6300: 1.542286 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.01\n",
      "Validation set perplexity: 4.23\n",
      "Average loss at step 6400: 1.541274 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.56\n",
      "Validation set perplexity: 4.22\n",
      "Average loss at step 6500: 1.556857 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.56\n",
      "Validation set perplexity: 4.21\n",
      "Average loss at step 6600: 1.594493 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.91\n",
      "Validation set perplexity: 4.20\n",
      "Average loss at step 6700: 1.577920 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.22\n",
      "Validation set perplexity: 4.23\n",
      "Average loss at step 6800: 1.597577 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.71\n",
      "Validation set perplexity: 4.24\n",
      "Average loss at step 6900: 1.577417 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.71\n",
      "Validation set perplexity: 4.23\n",
      "Average loss at step 7000: 1.572932 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.99\n",
      "================================================================================\n",
      " one nine nine five nine one confincts call srickin of moving to of these one vi\n",
      "phising pospi one gip both right dirge kilnctorm the struap to lasters in dai bu\n",
      "ed appovence onleine americation as an the congress not shap three one three six\n",
      "ptictly see into orbiah in the pneden possing of it rebrise nine the feltes seco\n",
      "namip to sumboms spairalt modern pained in enumanis sets were effocually caps to\n",
      "================================================================================\n",
      "Validation set perplexity: 4.21\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 100\n",
    "\n",
    "with tf.Session(graph=graph) as session:\n",
    "  tf.initialize_all_variables().run()\n",
    "  print('Initialized')\n",
    "  mean_loss = 0\n",
    "  for step in range(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in range(num_unrollings + 1):\n",
    "      feed_dict[train_data[i]] = batches[i]\n",
    "    _, l, predictions, lr = session.run(\n",
    "      [optimizer, loss, train_prediction, learning_rate], feed_dict=feed_dict)\n",
    "    mean_loss += l\n",
    "    if step % summary_frequency == 0:\n",
    "      if step > 0:\n",
    "        mean_loss = mean_loss / summary_frequency\n",
    "      # The mean loss is an estimate of the loss over the last few batches.\n",
    "      print(\n",
    "        'Average loss at step %d: %f learning rate: %f' % (step, mean_loss, lr))\n",
    "      mean_loss = 0\n",
    "      labels = np.concatenate(list(batches)[1:])\n",
    "      print('Minibatch perplexity: %.2f' % float(\n",
    "        np.exp(logprob(predictions, labels))))\n",
    "      if step % (summary_frequency * 10) == 0:\n",
    "        # Generate some samples.\n",
    "        print('=' * 80)\n",
    "        for _ in range(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in range(79):\n",
    "            prediction = sample_prediction.eval({sample_input: feed})\n",
    "            feed = sample(prediction)\n",
    "            sentence += characters(feed)[0]\n",
    "          print(sentence)\n",
    "        print('=' * 80)\n",
    "      # Measure validation set perplexity.\n",
    "      reset_sample_state.run()\n",
    "      valid_logprob = 0\n",
    "      for _ in range(valid_size):\n",
    "        b = valid_batches.next()\n",
    "        predictions = sample_prediction.eval({sample_input: b[0]})\n",
    "        valid_logprob = valid_logprob + logprob(predictions, b[1])\n",
    "      print('Validation set perplexity: %.2f' % float(np.exp(\n",
    "        valid_logprob / valid_size)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "pl4vtmFfa5nn"
   },
   "source": [
    "---\n",
    "Problem 1\n",
    "---------\n",
    "\n",
    "You might have noticed that the definition of the LSTM cell involves 4 matrix multiplications with the input, and 4 matrix multiplications with the output. Simplify the expression by using a single matrix multiply for each, and variables that are 4 times larger."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "num_nodes = 64\n",
    "\n",
    "graph = tf.Graph()\n",
    "with graph.as_default():\n",
    "  \n",
    "  # Parameters: \n",
    "  # Single matrix: input, previous output, and bias.\n",
    "  ifcox = tf.Variable(tf.truncated_normal([vocabulary_size, 4 * num_nodes], -0.1, 0.1))\n",
    "  ifcom = tf.Variable(tf.truncated_normal([num_nodes, 4 * num_nodes], -0.1, 0.1))\n",
    "  ifcob = tf.Variable(tf.zeros([1, 4 * num_nodes]))\n",
    "  # Variables saving state across unrollings.\n",
    "  saved_output = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  saved_state = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  # Classifier weights and biases.\n",
    "  w = tf.Variable(tf.truncated_normal([num_nodes, vocabulary_size], -0.1, 0.1))\n",
    "  b = tf.Variable(tf.zeros([vocabulary_size]))\n",
    "  \n",
    "  # Definition of the cell computation.\n",
    "  def lstm_cell(i, o, state):\n",
    "    \"\"\"Create a LSTM cell. See e.g.: http://arxiv.org/pdf/1402.1128v1.pdf\n",
    "    Note that in this formulation, we omit the various connections between the\n",
    "    previous state and the gates.\"\"\"\n",
    "    all_gates_state = tf.matmul(i, ifcox) + tf.matmul(o, ifcom) + ifcob\n",
    "    input_gate = tf.sigmoid(all_gates_state[:, 0:num_nodes])\n",
    "    forget_gate = tf.sigmoid(all_gates_state[:, num_nodes: 2 * num_nodes])\n",
    "    update = all_gates_state[:, 2 * num_nodes: 3 * num_nodes]\n",
    "    state = forget_gate * state + input_gate * tf.tanh(update)\n",
    "    output_gate = tf.sigmoid(all_gates_state[:, 3 * num_nodes:])\n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "  for _ in range(num_unrollings + 1):\n",
    "    train_data.append(\n",
    "      tf.placeholder(tf.float32, shape=[batch_size,vocabulary_size]))\n",
    "  train_inputs = train_data[:num_unrollings]\n",
    "  train_labels = train_data[1:]  # labels are inputs shifted by one time step.\n",
    "\n",
    "  # Unrolled LSTM loop.\n",
    "  outputs = list()\n",
    "  output = saved_output\n",
    "  state = saved_state\n",
    "  for i in train_inputs:\n",
    "    output, state = lstm_cell(i, output, state)\n",
    "    outputs.append(output)\n",
    "\n",
    "  # State saving across unrollings.\n",
    "  with tf.control_dependencies([saved_output.assign(output),\n",
    "                                saved_state.assign(state)]):\n",
    "    # Classifier.\n",
    "    logits = tf.nn.xw_plus_b(tf.concat(0, outputs), w, b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        logits, tf.concat(0, train_labels)))\n",
    "\n",
    "  # Optimizer.\n",
    "  global_step = tf.Variable(0)\n",
    "  learning_rate = tf.train.exponential_decay(\n",
    "    10.0, global_step, 5000, 0.1, staircase=True)\n",
    "  optimizer = tf.train.GradientDescentOptimizer(learning_rate)\n",
    "  gradients, v = zip(*optimizer.compute_gradients(loss))\n",
    "  gradients, _ = tf.clip_by_global_norm(gradients, 1.25)\n",
    "  optimizer = optimizer.apply_gradients(\n",
    "    zip(gradients, v), global_step=global_step)\n",
    "\n",
    "  # Predictions.\n",
    "  train_prediction = tf.nn.softmax(logits)\n",
    "  \n",
    "  # Sampling and validation eval: batch 1, no unrolling.\n",
    "  sample_input = tf.placeholder(tf.float32, shape=[1, vocabulary_size])\n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  reset_sample_state = tf.group(\n",
    "    saved_sample_output.assign(tf.zeros([1, num_nodes])),\n",
    "    saved_sample_state.assign(tf.zeros([1, num_nodes])))\n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input, saved_sample_output, saved_sample_state)\n",
    "  with tf.control_dependencies([saved_sample_output.assign(sample_output),\n",
    "                                saved_sample_state.assign(sample_state)]):\n",
    "    sample_prediction = tf.nn.softmax(tf.nn.xw_plus_b(sample_output, w, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0: 3.293514 learning rate: 10.000000\n",
      "Minibatch perplexity: 26.94\n",
      "================================================================================\n",
      "takna fias etlxhnt soidthkvax r ik h gecseeujqdi vu se t  gc er fcuoafkjj t  wtm\n",
      "lwocetneyv lranerivatacqecuahvcdja  itzefr eiodt kcxcxe e dnh cfl eue tuylrngjym\n",
      "z eai kwtnektnzusunpeevfet vt esnherreaevthlh aetre  e  vcczntgcxdt soeh w u zro\n",
      "f vtebedragheewtqrgfi mvq jnasr aruzozcelpzdbiiz zh dweabjd ycyhzwe vntpry acdav\n",
      "qfupgem ig    n rxdisis ktewrg ezusn r lkrao  awo ea iay iqz wr iib r t beouanik\n",
      "================================================================================\n",
      "Validation set perplexity: 20.17\n",
      "Average loss at step 100: 2.589363 learning rate: 10.000000\n",
      "Minibatch perplexity: 10.86\n",
      "Validation set perplexity: 11.00\n",
      "Average loss at step 200: 2.255463 learning rate: 10.000000\n",
      "Minibatch perplexity: 8.59\n",
      "Validation set perplexity: 8.91\n",
      "Average loss at step 300: 2.091487 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.31\n",
      "Validation set perplexity: 8.10\n",
      "Average loss at step 400: 2.034219 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.73\n",
      "Validation set perplexity: 7.93\n",
      "Average loss at step 500: 1.981705 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.45\n",
      "Validation set perplexity: 7.27\n",
      "Average loss at step 600: 1.900491 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.55\n",
      "Validation set perplexity: 7.02\n",
      "Average loss at step 700: 1.871383 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.88\n",
      "Validation set perplexity: 6.75\n",
      "Average loss at step 800: 1.868330 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.06\n",
      "Validation set perplexity: 6.68\n",
      "Average loss at step 900: 1.845642 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.00\n",
      "Validation set perplexity: 6.50\n",
      "Average loss at step 1000: 1.847980 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.45\n",
      "================================================================================\n",
      "mers the sean dists knaction k one zero five seven four f s n which in maces of \n",
      "rezs and cant s k usy moone in three hn two pirsuned and tramins sporice overida\n",
      "zerilid duntral costems a more furer cast one eight even five four it eight eigh\n",
      "t ismecis the tract counght cinss wilker the omaser are flove s one one zero zed\n",
      " to one opter and merach is juce ussire bcoasion vunalar de is of mus hyropir zo\n",
      "================================================================================\n",
      "Validation set perplexity: 6.30\n",
      "Average loss at step 1100: 1.804735 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.38\n",
      "Validation set perplexity: 6.23\n",
      "Average loss at step 1200: 1.774345 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.37\n",
      "Validation set perplexity: 6.10\n",
      "Average loss at step 1300: 1.758540 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.90\n",
      "Validation set perplexity: 5.87\n",
      "Average loss at step 1400: 1.763826 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.16\n",
      "Validation set perplexity: 5.80\n",
      "Average loss at step 1500: 1.748162 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.63\n",
      "Validation set perplexity: 5.62\n",
      "Average loss at step 1600: 1.732263 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.48\n",
      "Validation set perplexity: 5.78\n",
      "Average loss at step 1700: 1.714223 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.22\n",
      "Validation set perplexity: 5.55\n",
      "Average loss at step 1800: 1.692898 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.96\n",
      "Validation set perplexity: 5.40\n",
      "Average loss at step 1900: 1.693331 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 5.52\n",
      "Average loss at step 2000: 1.681456 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.03\n",
      "================================================================================\n",
      "bereus yub eact and featic the quetion suctor lequee seffentssing a kide s one f\n",
      "y to all winte poroceas ada sevile uncluve th s was nect fines the are natled it\n",
      "wared thoughtes inclidfes is prizage getten for to where ices operational americ\n",
      "ing in playited that the tise mostly se four of wimed after lathes and phicch a \n",
      "p for brance it meanied bloonish the ejeptiig companits plane ratef bospheraliqu\n",
      "================================================================================\n",
      "Validation set perplexity: 5.43\n",
      "Average loss at step 2100: 1.688033 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.96\n",
      "Validation set perplexity: 5.42\n",
      "Average loss at step 2200: 1.706119 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.10\n",
      "Validation set perplexity: 5.48\n",
      "Average loss at step 2300: 1.707902 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.26\n",
      "Validation set perplexity: 5.37\n",
      "Average loss at step 2400: 1.686341 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.77\n",
      "Validation set perplexity: 5.37\n",
      "Average loss at step 2500: 1.689599 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.05\n",
      "Validation set perplexity: 5.38\n",
      "Average loss at step 2600: 1.672528 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.11\n",
      "Validation set perplexity: 5.31\n",
      "Average loss at step 2700: 1.684963 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.13\n",
      "Validation set perplexity: 5.39\n",
      "Average loss at step 2800: 1.684219 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.32\n",
      "Validation set perplexity: 5.40\n",
      "Average loss at step 2900: 1.673016 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.13\n",
      "Validation set perplexity: 5.31\n",
      "Average loss at step 3000: 1.682736 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.90\n",
      "================================================================================\n",
      "antula wedev calledia isun trin and of surts france as a x reform the retorian i\n",
      "netered second to roun it of the selvidmencand agreefubio corugibi orgency two h\n",
      "d and mich quand as of k of one two one fed in otvers of one ver in otric the tr\n",
      "half crosed use aboviman was and the for hast historted in of knonied its effect\n",
      "porting ivelly apapotency and bead claints the list hearting tht corig to typenc\n",
      "================================================================================\n",
      "Validation set perplexity: 5.20\n",
      "Average loss at step 3100: 1.650915 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.11\n",
      "Validation set perplexity: 5.19\n",
      "Average loss at step 3200: 1.637876 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.43\n",
      "Validation set perplexity: 5.02\n",
      "Average loss at step 3300: 1.646810 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.11\n",
      "Validation set perplexity: 5.05\n",
      "Average loss at step 3400: 1.633313 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.29\n",
      "Validation set perplexity: 5.09\n",
      "Average loss at step 3500: 1.675020 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.16\n",
      "Validation set perplexity: 5.09\n",
      "Average loss at step 3600: 1.650719 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.20\n",
      "Validation set perplexity: 5.03\n",
      "Average loss at step 3700: 1.651510 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.98\n",
      "Validation set perplexity: 5.09\n",
      "Average loss at step 3800: 1.660006 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.84\n",
      "Validation set perplexity: 5.06\n",
      "Average loss at step 3900: 1.651227 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.24\n",
      "Validation set perplexity: 5.05\n",
      "Average loss at step 4000: 1.639610 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.31\n",
      "================================================================================\n",
      "grave nation authors strict scients several battly of into soultza tam and forn \n",
      "ating and and an use boike referenting this reference of time prese same capap a\n",
      "tings to only from companiag peoples of as endey math which gamamat basks alth k\n",
      "ne resurasorf six by uniors of aftelly as the which can such deptesscessed by la\n",
      "y liqual copet and of the tructaks than of home wim anotox player american she o\n",
      "================================================================================\n",
      "Validation set perplexity: 5.02\n",
      "Average loss at step 4100: 1.623298 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.85\n",
      "Validation set perplexity: 4.95\n",
      "Average loss at step 4200: 1.617264 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.86\n",
      "Validation set perplexity: 4.96\n",
      "Average loss at step 4300: 1.619666 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.59\n",
      "Validation set perplexity: 5.12\n",
      "Average loss at step 4400: 1.609674 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.29\n",
      "Validation set perplexity: 5.06\n",
      "Average loss at step 4500: 1.639898 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.31\n",
      "Validation set perplexity: 5.18\n",
      "Average loss at step 4600: 1.625711 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.35\n",
      "Validation set perplexity: 4.91\n",
      "Average loss at step 4700: 1.623639 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.86\n",
      "Validation set perplexity: 4.99\n",
      "Average loss at step 4800: 1.605041 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.68\n",
      "Validation set perplexity: 4.92\n",
      "Average loss at step 4900: 1.617471 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.94\n",
      "Validation set perplexity: 4.82\n",
      "Average loss at step 5000: 1.617236 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.97\n",
      "================================================================================\n",
      "eish organion safus at clested on way encluncel in gring woven two venos juigit \n",
      "cha of nevai in the lare nummen gone power in the to dpplinoc of the dwc lond re\n",
      "y one nine nine six one zero k hads also todetical the for kance in forc of chan\n",
      "ism frances formal davishs dourchanng a crittwes one samolad and liled in the se\n",
      "jorchwolgour brews unreme played therevoule consisting dan namenss of the molaxa\n",
      "================================================================================\n",
      "Validation set perplexity: 4.91\n",
      "Average loss at step 5100: 1.588928 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.97\n",
      "Validation set perplexity: 4.81\n",
      "Average loss at step 5200: 1.593373 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.21\n",
      "Validation set perplexity: 4.77\n",
      "Average loss at step 5300: 1.594800 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.28\n",
      "Validation set perplexity: 4.77\n",
      "Average loss at step 5400: 1.590659 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.65\n",
      "Validation set perplexity: 4.70\n",
      "Average loss at step 5500: 1.589930 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.37\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 5600: 1.564814 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.35\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 5700: 1.582732 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.71\n",
      "Validation set perplexity: 4.61\n",
      "Average loss at step 5800: 1.600458 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.70\n",
      "Validation set perplexity: 4.65\n",
      "Average loss at step 5900: 1.581863 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.22\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 6000: 1.588996 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.89\n",
      "================================================================================\n",
      "quoza doumobined expars and favel systen iellated and throur notion at fingwary \n",
      "e whosed america and princell leadivious lard rehugion american who where from s\n",
      "lomay daired asselseas ligarly vethes that the dimack experdency daminal was may\n",
      "k that maistablia liever mean althoughlic ordersulenta two two three th todes ob\n",
      "ly state say war sciented this his leadoun detartic of the seven thro sist the b\n",
      "================================================================================\n",
      "Validation set perplexity: 4.60\n",
      "Average loss at step 6100: 1.578299 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.59\n",
      "Validation set perplexity: 4.63\n",
      "Average loss at step 6200: 1.586613 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.73\n",
      "Validation set perplexity: 4.65\n",
      "Average loss at step 6300: 1.585297 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.30\n",
      "Validation set perplexity: 4.65\n",
      "Average loss at step 6400: 1.572586 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.20\n",
      "Validation set perplexity: 4.70\n",
      "Average loss at step 6500: 1.557851 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.30\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 6600: 1.599996 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.85\n",
      "Validation set perplexity: 4.68\n",
      "Average loss at step 6700: 1.575205 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.49\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 6800: 1.580816 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.77\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 6900: 1.576813 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.60\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 7000: 1.590353 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.75\n",
      "================================================================================\n",
      "ing all i velcodogiss to humant deright boog daugh murchitical continue edeing h\n",
      "y riffilment began acagent often the whether ledinont assistens an achnametic wa\n",
      "il in the aseed critication bedvoned celmation at timisment of nighteng was of t\n",
      "ly secially driditiualf nast nine interd out and maryuess of tweat humbo impline\n",
      "arcent as new annhory ediging expained usxian pincture and strought recurs maze \n",
      "================================================================================\n",
      "Validation set perplexity: 4.67\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 100\n",
    "\n",
    "with tf.Session(graph=graph) as session:\n",
    "  tf.initialize_all_variables().run()\n",
    "  print('Initialized')\n",
    "  mean_loss = 0\n",
    "  for step in range(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in range(num_unrollings + 1):\n",
    "      feed_dict[train_data[i]] = batches[i]\n",
    "    _, l, predictions, lr = session.run(\n",
    "      [optimizer, loss, train_prediction, learning_rate], feed_dict=feed_dict)\n",
    "    mean_loss += l\n",
    "    if step % summary_frequency == 0:\n",
    "      if step > 0:\n",
    "        mean_loss = mean_loss / summary_frequency\n",
    "      # The mean loss is an estimate of the loss over the last few batches.\n",
    "      print(\n",
    "        'Average loss at step %d: %f learning rate: %f' % (step, mean_loss, lr))\n",
    "      mean_loss = 0\n",
    "      labels = np.concatenate(list(batches)[1:])\n",
    "      print('Minibatch perplexity: %.2f' % float(\n",
    "        np.exp(logprob(predictions, labels))))\n",
    "      if step % (summary_frequency * 10) == 0:\n",
    "        # Generate some samples.\n",
    "        print('=' * 80)\n",
    "        for _ in range(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in range(79):\n",
    "            prediction = sample_prediction.eval({sample_input: feed})\n",
    "            feed = sample(prediction)\n",
    "            sentence += characters(feed)[0]\n",
    "          print(sentence)\n",
    "        print('=' * 80)\n",
    "      # Measure validation set perplexity.\n",
    "      reset_sample_state.run()\n",
    "      valid_logprob = 0\n",
    "      for _ in range(valid_size):\n",
    "        b = valid_batches.next()\n",
    "        predictions = sample_prediction.eval({sample_input: b[0]})\n",
    "        valid_logprob = valid_logprob + logprob(predictions, b[1])\n",
    "      print('Validation set perplexity: %.2f' % float(np.exp(\n",
    "        valid_logprob / valid_size)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4eErTCTybtph"
   },
   "source": [
    "---\n",
    "Problem 2\n",
    "---------\n",
    "\n",
    "We want to train a LSTM over bigrams, that is pairs of consecutive characters like 'ab' instead of single characters like 'a'. Since the number of possible bigrams is large, feeding them directly to the LSTM using 1-hot encodings will lead to a very sparse representation that is very wasteful computationally.\n",
    "\n",
    "a- Introduce an embedding lookup on the inputs, and feed the embeddings to the LSTM cell instead of the inputs themselves.\n",
    "\n",
    "b- Write a bigram-based LSTM, modeled on the character LSTM above.\n",
    "\n",
    "c- Introduce Dropout. For best practices on how to use Dropout in LSTMs, refer to this [article](http://arxiv.org/abs/1409.2329)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Y5tapX3kpcqZ"
   },
   "source": [
    "---\n",
    "Problem 3\n",
    "---------\n",
    "\n",
    "(difficult!)\n",
    "\n",
    "Write a sequence-to-sequence LSTM which mirrors all the words in a sentence. For example, if your input is:\n",
    "\n",
    "    the quick brown fox\n",
    "    \n",
    "the model should attempt to output:\n",
    "\n",
    "    eht kciuq nworb xof\n",
    "    \n",
    "Refer to the lecture on how to put together a sequence-to-sequence model, as well as [this article](http://arxiv.org/abs/1409.3215) for best practices."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "default_view": {},
   "name": "6_lstm.ipynb",
   "provenance": [],
   "version": "0.3.2",
   "views": {}
  },
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
